The present invention relates to image processing and, more particularly, to a method for rendering an image comprising pixels renderable at one of a plurality of intensity levels.
Typically, digital images are stored and processed as an array of picture elements or pixels. Each pixel represents the intensity of the image when sampled at a set of spatial coordinates defined by a grid that virtually overlays the image. The analog signal obtained by sampling the image at the pixel's location is quantized to a discrete value known as a gray scale level that is proportional to the amplitude of the intensity or reflectance of the sample. In the case of a monochrome image, the gray scale value of a pixel is a quantized scalar representation of the intensity. On the other hand, the value of a pixel of a color image is a vector representing the combined intensities of a plurality of component colors (for example, red, green, and blue) of the pixel. A color image is, in effect, a plurality of superimposed gray scale images where the intensity of a pixel of one of the gray scale images represents the intensity of a component color at the pixel's location.
The human visual system can resolve approximately 200 levels of intensity and image sampling devices and processes, such as scanners, cameras, and computer graphics programs, commonly resolve intensity to 256 or more levels. With 256 levels of intensity resolution for each of three color components, one of approximately 16.7 million colors can be specified for each pixel of a color image. Images comprising pixels specified with such fine resolution are known as continuous tone images, even though the possible values of pixel intensity vary by finite, non-zero amounts.
In contrast to the fine resolution that can be quantified by a typical image sampling device or process, image display devices can produce pixels with very few intensity levels. For example, a bi-tonal printer can deposit or not deposit ink at a pixel location to render the pixel either black (or one of the component colors) or white. On the other hand, some display devices are capable of producing pixels with a plurality of intensity levels, increasing the diversity of pixel intensity in the displayed image. For example, some printers are capable of varying the size of the dot deposited or selecting among a plurality of shades of printing medium to deposit at a pixel and some cathode ray tube (CRT) displays can display several pixel intensities by altering the strength of the electron beam incident upon the phosphor at the pixel location. However, the number of intensity levels that can be displayed by most display devices is very limited compared to the large number of levels that can be captured by sampling an image.
Techniques known generally as digital halftoning are used to produce images that have the appearance of a continuous tone image even though the pixels of the halftone image are rendered with relatively few levels of resolution compared to the resolution of the sampled continuous tone image. Generally, digital halftoning is a technique that outputs an image that is subdivided into a plurality of areas known as halftone cells. The halftone cells contain a number dots that are arranged and rendered such that the halftone cell will be perceived by a viewer to have a gray scale intensity commensurate with that of the corresponding area of a continuous tone image.
The process of mapping the intensity samples or input pixels from areas of a continuous tone image to an arrangement of dots comprising one or device pixels in a halftone cell is known as spatial modulation. Spatial modulation is accomplished by dithering, a process of comparing a quantized gray scale intensity of an input pixel to an entry in a matrix of modulation levels that typically includes an entry for each pixel of the halftone cell. In bi-tonal halftoning, if the intensity of the input pixel exceeds the modulation level, a signal is sent to the printer or other display device and a dot is created (for example, ink is deposited) in the output image at a location corresponding to the pixel's location in the input image. If the intensity value is less than the modulation level, a dot is not created at the pixel. The matrix comparison process is repeated for each input pixel from the continuous tone image. As a result, the continuous tone input image is converted to a halftone image comprising a tile-like arrangement of multiple dot, halftone cells which are intended to be perceptually equivalent to corresponding areas of the continuous tone image. To create a color image, the interlaced color data representing an image sample is separated into the data representing each individual color component (typically red, green, and blue or cyan, magenta, yellow, and black) and the halftoning process is repeated for each color component of each image pixel. The halftone images for each of the color components are overlaid to create the halftone color image.
Multi-level halftoning is an extension of bi-tonal halftoning in which the output dot or pixel is rendered at one of the several available intensity levels rather than the two levels (ON or OFF, INK or NO INK) available with bi-tonal halftoning. If a display device can accurately display five levels of intensity at a device pixel or dot, the multi-level halftoning system simulates the appearance of an area of a continuous tone image by distributing in a halftone cell a plurality of dots, each having one of five possible intensity levels. The bi-tonal dithering process is extended to determine the appropriate intensity level of the multi-level output dot or device pixel. The intensity of the input sample is compared to an entry in each of N−1 modulation level matrices, where N is the number of available output intensity levels for the device pixel. The output of each comparison is represented by a digital bit having a value of either logical “1” if the input intensity is greater than the modulation level or logical “0” if the input intensity is less than the modulation level. Each output bit is stored in an intermediate matrix that is, in essence, a bi-tonal halftone cell. The elements of the intermediate matrix are combined to form a multi-bit value that is encoded to select one of the available output intensity levels for the multi-level device pixel or dot to be rendered in the halftone cell. To reduce the computation required for halftoning with multi-level pixels, the results of coding of the several comparisons can be captured in a transfer function that is selected by the input sample location and which yields an output intensity level corresponding to an intensity of an input sample.
While multi-level dots or device pixels increase the diversity of the dots in the output halftone cell, potentially facilitating more faithful reproduction of the appearance of a continuous tone image, the strategies for intensity change or growth of multi-level pixels have generally been an extension of the intensity growth of bi-tonal pixels and produce less than optimal results. Multi-level pixel intensity growth has followed either a hard dot or soft dot strategy. In the hard dot strategy, a second dot or pixel is not printed (the pixel's intensity is not increased from the minimum level) unless the intensity of a first dot or pixel in the cell is at the maximum level. Following the soft dot strategy, the intensities of a plurality of pixels grow simultaneously to increase the intensity of the halftone cell. The hard dot strategy produces sharper images with higher contrast than the soft dot strategy, but images created with the soft dot growth strategy are more detailed than images produced with the hard dot strategy.
What is desired, therefore, is a method for rendering multi-level pixels in a halftone cell to produce an image having the appearance and the detail of a continuous tone image.